package baseTest;

import java.util.HashMap;

class Node{
    public Integer key;
    public Integer value;
    public Integer times;
    public Node up;
    public Node down;

    public Node(int key,int value,int times){
        this.key = key;
        this.value = value;
        this.times = times;
    }
}

class NodeList{
    public Node head; //桶结点
    public Node tail; //桶的尾结点
    public NodeList last; //桶结点之间是一个双向链表，所以有前一个桶
    public NodeList next;//桶结点之间是一个双向链表，所以有后一个桶

    public NodeList(Node node){
        head = node;
        tail = node;
    }
    //把一个新的结点加入到这个桶，新的节点都放在顶端变成新的头部
    public void addNodeFromHead(Node newHead){
        newHead.down = newHead;
        head.up = newHead;
        head.down = newHead;
    }
    //判断这个桶是不是空的
    public boolean isEmpty(){
        return head == null;
    }
    //删除node结点并保证node的上下文重新连接
    public void deleteNode(Node node){
        if (head == tail){
            head = null;
            tail = null;
        } else {
            if (node == head){
                head = node.down;
                head.up = null;
            } else if (node == null){
                tail = node.up;
                tail.down = null;
            } else {
                node.up.down = node.down;
                node.down.up = node.up;
            }
        }
        node.up = null;
        node.down = null;
    }
}

public class LFUCache {

    private int capacity; //缓存大小限制
    private int size; //缓存目前多少个结点
    private HashMap<Integer, Node> records; //由哪个结点代表
    private HashMap<Node,NodeList> heads;//表示结点在哪个桶里
    private NodeList headList; //整个结构中位于最左的桶

}
